package com.yiwenup.leetcode.offer;

/**
 * https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/
 **/
public class No010 {
    public int fib(int n) {
        if (n < 2) return n;
        return fib(n - 1) + fib(n - 2);
    }

    public int fib2(int n) {
        int a = 0;
        int b = 1;
        if (n == 0) return 0;
        if (n == 1) return 1;
        int tmp = 0;
        for (int i = 2; i <= n; i++) {
            tmp = (a + b) % 1000000007;
            a = b;
            b = tmp;
        }
        return tmp;
    }

    /**
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：34.9 MB, 在所有 Java 提交中击败了96.58%的用户
     */
    public int fib3(int n) {
        if (n < 1) return 0;
        int[] memo = new int[n + 1];
        return dp(n, memo);
    }

    private int dp(int n, int[] memo) {
        if (n == 1 || n == 2) return 1;
        if (memo[n] != 0) return memo[n];
        memo[n] = (dp(n - 1, memo) + dp(n - 2, memo)) % 1000000007;
        return memo[n];
    }

    /**
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：35.1 MB, 在所有 Java 提交中击败了71.98%的用户
     */
    public int fib4(int n) {
        if (n < 1) return 0;
        if (n == 1 || n == 2) return 1;
        int[] memo = new int[n + 1];
        memo[1] = memo[2] = 1;
        for (int i = 3; i <= n; i++) {
            memo[i] = (memo[i - 1] + memo[i - 2]) % 1000000007;
        }
        return memo[n];
    }

    /**
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：34.9 MB, 在所有 Java 提交中击败了95.17%的用户
     */
    public int fib5(int n) {
        if (n < 1) return 0;
        if (n == 1 || n == 2) return 1;

        int pre = 1, cur = 1;
        int tmp;
        for (int i = 3; i <= n; i++) {
            tmp = (pre + cur) % 1000000007;
            pre = cur;
            cur = tmp;
        }

        return cur;
    }

    /**
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：35.2 MB, 在所有 Java 提交中击败了52.80%
     * 的用户
     */
    public int fib6(int n) {
        if (n <= 0) return 0;
        int[] arr = new int[2];
        arr[0] = arr[1] = 1;
        for (int i = 3; i <= n; i++) {
            arr[i & 1] = (arr[(i - 1) & 1] + arr[(i - 2) & 1]) % 1000000007;
        }
        return arr[n & 1];
    }
}
